package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 2406. 将区间分为最少组数
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/11 21:04
 */
public class MinGroups {

    public static void main(String[] args) {
        MinGroups test = new MinGroups();

        // 3
//        int[][] intervals = {{5, 10}, {6, 8}, {1, 5}, {2, 3}, {1, 10}};

        // 1
        int[][] intervals = {{1, 3}, {5, 6}, {8, 10}, {11, 13}};

        int i = test.minGroups(intervals);
        System.out.println(i);
    }

    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] interval : intervals) {
            Map.Entry<Integer, Integer> entry = map.floorEntry(interval[0] - 1);
            if (entry != null) {
                Integer value = entry.getValue();
                if (value == 1) {
                    map.remove(entry.getKey());
                } else {
                    map.put(entry.getKey(), value - 1);
                }
            }
            map.put(interval[1], map.getOrDefault(interval[1], 0) + 1);
        }
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
        }
        return sum;
    }

}
